package com.example.algorithm.divideAndConquer;

import java.util.*;

/**
 * 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。
 *  有效的运算符号包含 +, - 以及 *。
 *
 *  示例 1:
 *  输入: "2-1-1"
 * 输出: [0, 2]
 * 解释:
 * ((2-1)-1) = 0
 * (2-(1-1)) = 2
 *
 *  示例 2:
 *  输入: "2*3-4*5"
 * 输出: [-34, -14, -10, -10, 10]
 * 解释:
 * (2*(3-(4*5))) = -34
 * ((2*3)-(4*5)) = -14
 * ((2*(3-4))*5) = -10
 * (2*((3-4)*5)) = -10
 * (((2*3)-4)*5) = 10
 */
public class Leetcode241_DiffWaysToCompute {
    public static void main(String[] args) {
        String expression = "2*3-4*5";
        System.out.println(new Solution().diffWaysToCompute(expression));
    }

    static class Solution {
        /**
         * 优化，使用map将计算过的表达式的结果保存起来后面如果有用到直接取即可
         * @param expression
         * @return
         */
        Map<String, List<Integer>> cachedMap = new HashMap<>();
        private List<Integer> diffWaysToCompute2(String expression) {
            List<Integer> res = new ArrayList<>();
            if (cachedMap.containsKey(expression)) return cachedMap.get(expression); // 当前表达式已经计算过结果，直接就从map中获取后返回
            char[] chars = expression.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char curChar = chars[i];
                if (curChar == '+' || curChar == '-' || curChar == '*') {
                    List<Integer> leftRes = diffWaysToCompute(expression.substring(0, i));
                    List<Integer> rightRes = diffWaysToCompute(expression.substring(i + 1));

                    // 根据左右表达式和当前的运算符计算结果并放入集合中
                    for (Integer leftRe : leftRes) {
                        for (Integer rightRe : rightRes) {
                            switch (curChar) {
                                case '+':
                                    res.add(leftRe + rightRe);
                                    break;
                                case '-':
                                    res.add(leftRe - rightRe);
                                    break;
                                case '*':
                                    res.add(leftRe * rightRe);
                                    break;
                            }
                        }
                    }
                }
            }

            if (res.isEmpty()) {
                res.add(Integer.valueOf(expression));
            }
            cachedMap.put(expression, res); // 将当前表达式的结果"缓存"起来，如果后面有相同表达式则可以不再进行计算
            return res;
        }

        /**
         * 解法一：分治
         * 当前表达式中的每个运算符作为左右区间的划分标志,递归进行拆分
         * 以 2*3-4*5 为例
         * 差分如下:
         *  以第一个 '*' 拆分成左右两个子表达式 left = 2 right = 3-4*5 依次递归进行拆分直到表达式可以算出结果为止
         *     left已经是一个数字，就不再进行拆分， right拆分如下
         *      以 '-' 拆成 left = 3 right = 4*5
         *        left不再进行拆分，right以'*'拆分如下
         *          left = 4 right = 5
         *      以 '*' 拆成 left = 3-4 right = 5
         *        right不再进行拆分，left以'-'拆分为
         *         left = 3 right = 4
         *  以 '-' 拆分成左右两个子表达式 left = 2 * 3 right = 4*5 ....
         *
         * @param expression
         * @return
         */
        private List<Integer> diffWaysToCompute1(String expression) {
            if (expression == null || expression.length() == 0) return null;
            return diffWaysToCompute(expression.toCharArray());
        }

        private List<Integer> diffWaysToCompute(char[] experssion) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < experssion.length; i++) {
                char curChar = experssion[i];
                if (curChar == '+' || curChar == '-' || curChar == '*') { // 遇到运算符就要进行拆分
                    char[] leftExpression = new char[i];
                    System.arraycopy(experssion, 0, leftExpression, 0, i);
                    List<Integer> leftRes =  diffWaysToCompute(leftExpression); // 拆分并递归计算出左表达式的结果
                    char[] rightExpression = new char[experssion.length - i - 1];
                    System.arraycopy(experssion, i + 1, rightExpression, 0, rightExpression.length);
                    List<Integer> rightRes = diffWaysToCompute(rightExpression);// 拆分并递归计算出右表达式的结果

                    // 根据左右表达式和当前的运算符计算结果并放入集合中
                    for (Integer leftRe : leftRes) {
                        for (Integer rightRe : rightRes) {
                            switch (curChar) {
                                case '+':
                                    res.add(leftRe + rightRe);
                                    break;
                                case '-':
                                    res.add(leftRe - rightRe);
                                    break;
                                case '*':
                                    res.add(leftRe * rightRe);
                                    break;
                            }
                        }
                    }
                }

            }

            if (res.isEmpty()) {
                StringBuilder sb = new StringBuilder();
                for (char str : experssion) {
                    sb.append(str);
                }
                res.add(Integer.parseInt(sb.toString()));
            }
            return res;
        }

        public List<Integer> diffWaysToCompute(String expression) {
            return diffWaysToCompute2(expression);
        }
    }
}
